package hzip;
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

interface BitUtils {
	public static final int BITS_PER_BYTES = 8;
	public static final int DIFF_BYTES = 256;
	public static final int EOF = 256;
}

// BitInputStream class: Bit-input stream wrapper class.
//
// CONSTRUCTION: with an open InputStream.
//
// ******************PUBLIC OPERATIONS***********************
// int readBit( ) --> Read one bit as a 0 or 1
// void close( ) --> Close underlying stream

class BitInputStream {
	public BitInputStream(InputStream is) {
		in = is;
		bufferPos = BitUtils.BITS_PER_BYTES;
	}

	public int readBit() throws IOException {
		if (bufferPos == BitUtils.BITS_PER_BYTES) {
			buffer = in.read();
			if (buffer == -1)
				return -1;
			bufferPos = 0;
		}

		return getBit(buffer, bufferPos++);
	}

	public void close() throws IOException {
		in.close();
	}

	private static int getBit(int pack, int pos) {
		return (pack & (1 << pos)) != 0 ? 1 : 0;
	}

	private InputStream in;
	private int buffer;
	private int bufferPos;
}

// BitOutputStream class: Bit-output stream wrapper class.
//
// CONSTRUCTION: with an open OutputStream.
//
// ******************PUBLIC OPERATIONS***********************
// void writeBit( val ) --> Write one bit (0 or 1)
// void writeBits( vald ) --> Write array of bits
// void flush( ) --> Flush buffered bits
// void close( ) --> Close underlying stream

class BitOutputStream {
	public BitOutputStream(OutputStream os) {
		bufferPos = 0;
		buffer = 0;
		out = os;
	}

	public void writeBit(int val) throws IOException {
		buffer = setBit(buffer, bufferPos++, val);
		if (bufferPos == BitUtils.BITS_PER_BYTES)
			flush();
	}

	public void writeBits(int[] val) throws IOException {
		for (int v : val)
			writeBit(v);
	}

	public void flush() throws IOException {
		if (bufferPos == 0)
			return;

		out.write(buffer);
		bufferPos = 0;
		buffer = 0;
	}

	public void close() throws IOException {
		flush();
		out.close();
	}

	private int setBit(int pack, int pos, int val) {
		if (val == 1)
			pack |= (val << pos);
		return pack;
	}

	private OutputStream out;
	private int buffer;
	private int bufferPos;
}

// CharCounter class: A character counting class.
//
// CONSTRUCTION: with no parameters or an open InputStream.
//
// ******************PUBLIC OPERATIONS***********************
// int getCount( ch ) --> Return # occurrences of ch
// void setCount( ch, count ) --> Set # occurrences of ch
// ******************ERRORS**********************************
// No error checks.

class CharCounter {
	public CharCounter() {
	}

	public CharCounter(InputStream input) throws IOException {
		int ch;
		while ((ch = input.read()) != -1)
			theCounts[ch]++;
	}

	public int getCount(int ch) {
		return theCounts[ch & 0xff];
	}

	public void setCount(int ch, int count) {
		theCounts[ch & 0xff] = count;
	}

	private int[] theCounts = new int[BitUtils.DIFF_BYTES + 1];
}

// Basic node in a Huffman coding tree.
class HuffNode implements Comparable<HuffNode> {
	public int value;
	public int weight;

	public int compareTo(HuffNode rhs) {
		return weight - rhs.weight;
	}

	HuffNode left;
	HuffNode right;
	HuffNode parent;

	HuffNode(int v, int w, HuffNode lt, HuffNode rt, HuffNode pt) {
		value = v;
		weight = w;
		left = lt;
		right = rt;
		parent = pt;
	}
}

// Huffman tree class interface: manipulate huffman coding tree.
//
// CONSTRUCTION: with no parameters or a CharCounter object.
//
// ******************PUBLIC OPERATIONS***********************
// int [ ] getCode( ch ) --> Return code given character
// int getChar( code ) --> Return character given code
// void writeEncodingTable( out ) --> Write coding table to out
// void readEncodingTable( in ) --> Read encoding table from in
// ******************ERRORS**********************************
// Error check for illegal code.

class HuffmanTree {
	public HuffmanTree() {
		theCounts = new CharCounter();
		root = null;
	}

	public HuffmanTree(CharCounter cc) {
		theCounts = cc;
		root = null;
		createTree();
	}

	public static final int ERROR = -3;
	public static final int INCOMPLETE_CODE = -2;
	public static final int END = BitUtils.DIFF_BYTES;

	/**
	 * Return the code corresponding to character ch. (The parameter is an int
	 * to accomodate EOF). If code is not found, return an array of length 0.
	 */
	public int[] getCode(int ch) {
		HuffNode current = theNodes[ch];
		if (current == null)
			return null;

		String v = "";
		HuffNode par = current.parent;

		while (par != null) {
			if (par.left == current)
				v = "0" + v;
			else
				v = "1" + v;
			current = current.parent;
			par = current.parent;
		}

		int[] result = new int[v.length()];
		for (int i = 0; i < result.length; i++)
			result[i] = v.charAt(i) == '0' ? 0 : 1;

		return result;
	}

	/**
	 * Get the character corresponding to code.
	 */
	public int getChar(String code) {
		HuffNode p = root;
		for (int i = 0; p != null && i < code.length(); i++)
			if (code.charAt(i) == '0')
				p = p.left;
			else
				p = p.right;

		if (p == null)
			return ERROR;

		return p.value;
	}

	// Write the encoding table using character counts
	/**
	 * Writes an encoding table to an output stream. Format is character, count
	 * (as bytes). A zero count terminates the encoding table.
	 */
	public void writeEncodingTable(DataOutputStream out) throws IOException {
		for (int i = 0; i < BitUtils.DIFF_BYTES; i++) {
			if (theCounts.getCount(i) > 0) {
				out.writeByte(i);
				out.writeInt(theCounts.getCount(i));
			}
		}
		out.writeByte(0);
		out.writeInt(0);
	}

	/**
	 * Read the encoding table from an input stream in format given above and
	 * then construct the Huffman tree. Stream will then be positioned to read
	 * compressed data.
	 */
	public void readEncodingTable(DataInputStream in) throws IOException {
		for (int i = 0; i < BitUtils.DIFF_BYTES; i++)
			theCounts.setCount(i, 0);

		int ch;
		int num;

		for (;;) {
			ch = in.readByte();
			num = in.readInt();
			if (num == 0)
				break;
			theCounts.setCount(ch, num);
		}

		createTree();
	}

	/**
	 * Construct the Huffman coding tree.
	 */
	private void createTree() {
		java.util.PriorityQueue<HuffNode> pq = new java.util.PriorityQueue<HuffNode>();

		for (int i = 0; i < BitUtils.DIFF_BYTES; i++)
			if (theCounts.getCount(i) > 0) {
				HuffNode newNode = new HuffNode(i, theCounts.getCount(i), null,
						null, null);
				theNodes[i] = newNode;
				pq.offer(newNode);
			}

		theNodes[END] = new HuffNode(END, 1, null, null, null);
		pq.offer(theNodes[END]);

		while (pq.size() > 1) {
			HuffNode n1 = pq.poll();
			HuffNode n2 = pq.poll();
			HuffNode result = new HuffNode(INCOMPLETE_CODE, n1.weight
					+ n2.weight, n1, n2, null);
			n1.parent = n2.parent = result;
			pq.offer(result);
		}

		root = pq.peek();
	}

	private CharCounter theCounts;
	private HuffNode[] theNodes = new HuffNode[BitUtils.DIFF_BYTES + 1];
	private HuffNode root;
}

public class Hzip {

	public static void compress(String inFile) throws IOException {
		String compressedFile = inFile + ".huf";
		InputStream in = new BufferedInputStream(new FileInputStream(inFile));
		OutputStream fout = new BufferedOutputStream(new FileOutputStream(
				compressedFile));
		HZIPOutputStream hzout = new HZIPOutputStream(fout);
		int ch;
		while ((ch = in.read()) != -1)
			hzout.write(ch);
		in.close();
		hzout.close();
	}

	public static void uncompress(String compressedFile) throws IOException {
		String inFile;
		String extension;

		inFile = compressedFile.substring(0, compressedFile.length() - 4);
		extension = compressedFile.substring(compressedFile.length() - 4);

		if (!extension.equals(".huf")) {
			System.out.println("Not a compressed file!");
			return;
		}

		inFile += ".uc"; // for debugging, so as to not clobber original
		InputStream fin = new BufferedInputStream(new FileInputStream(
				compressedFile));
		DataInputStream in = new DataInputStream(fin);
		HZIPInputStream hzin = new HZIPInputStream(in);

		OutputStream fout = new BufferedOutputStream(new FileOutputStream(
				inFile));
		int ch;
		while ((ch = hzin.read()) != -1)
			fout.write(ch);

		hzin.close();
		fout.close();
	}

	public static void main(String[] args) throws IOException {
		if (args.length < 2) {
			System.out.println("Usage: java Hzip -[cu] files");
			return;
		}

		String option = args[0];
		for (int i = 1; i < args.length; i++) {
			String nextFile = args[i];
			if (option.equals("-c"))
				compress(nextFile);
			else if (option.equals("-u"))
				uncompress(nextFile);
			else {
				System.out.println("Usage: java Hzip -[cu] files");
				return;
			}
		}
	}
}
